Math 512: Finite Model Theory Generalized Quantifiers 0-1 Laws

John Baldwin

March 9, 1997

References: E and F chapter 10, Dawar and Gradel, Generalized Quantifiers and 0-1 laws - on web under papers at fmt site.

0.1 Definition. Fix two vocabularies σ and τ = ⟨R_{1} … R_{n}⟩. Let Ψ be a set of n formulas of vocabulary σ such that the arity of ψ_{i} is the same as that of R_{i}, say s_{i}. Then each σ-structure A determines a τ structure B = ΨA by interpreting R_{i} as ψ_{i}(A). (This can also, and this is an important extension, be done with parameters in the ψ_{i}.)

Now let K be collection of τ-structures. The quantifier Q_{K} is defined as follows. If Φ is a sequence of n-formulas (with ϕ_{i}, s_{i}-ary) then Q_{K}Φ is a formula and

A ⊧ Q_{K}Φ iff ΦA ∈ K.

0.2 Example. 1. τ contains a single unary predicate symbol; K = {⟨A, X⟩ : X ≠ ∅} is an esoteric way to define the existential quantifier.

2. τ contains a single unary predicate symbol; K = {⟨A, X⟩ : |X| ≥ n} is the counting quantifier, ‘there exists at least n’.

3. τ contains a single binary predicate symbol; K = {⟨A, R⟩ : R is the edge relation of a connected graph } is , ‘there exists a connected graph’.

More specifically, we define

0.3 Definition. For any class L of formulas in the relation symbol E, and any class of graphs closed under isomorphism, the graph quantifier Q_{H}^{G}. If ϕ(x, y, \overline{z}) is a formula so is Q_{H}^{G}ϕ(x, y, \overline{z}) which has \overline{z} free and (A, E) ⊧ Q_{H}^{G}ϕ(x, y, \overline{a}) if and only if \{⟨g_{1}, g_{2}⟩ : (A, E) ⊧ ϕ(g_{1}, g_{2}, \overline{a}) ∨ ϕ(g_{1}, g_{2}, \overline{a}) is in the class H.

Recall that a graph is Eulerian if there is a circuit of the graph which covers each edge exactly once. Thus, a finite connected graph is Eulerian if and only if each vertex has degree 2. A graph is Hamiltonian if there is a circuit of the graph in which every vertex except the first appears exactly once. A structure is rigid if it has no non-identity automorphism.

Now, further examples of generalized quantifiers are ”There exists a Hamiltonian graph” etc.

Let F O(Q_{K}) denote the extension of first order logic by the generalized quantifier Q_{K} and F O^{r}(Q_{K}) the fragment containing only generalized quantifiers: Q_{H}^{G}ϕ(x, y) (no parameters, no iteration).

0.4 Example. The probability that a graph is Eulerian (for constant probability p : 0 ≤ p < 1) is 0. (Exercise: like the probabilities we have computed before). However, F 0^{r}[Eul] does not satisfy the 0 − 1 law for any p. For, the formula

[Eulx, y]x ≠ y

is true in a graph n if and only if |G| is odd.

This situation is partially explained by

Theorem 0.5 (Dawar-Gradel). For each graph property H, F O^{r}[Q_{H}^{G}] satisfies the 0-1 law just if H has asymptotic probability 0 or 1 for each the class of graphs with edge probability 0, 1, p, and 1 − p.

Proof. Recall that the almost sure theory of random graphs is quantifier eliminable. Thus in a sentence Q_{H}^{G}ϕ(x, y), almost surely ϕ(x, y) is one of true, false, Rxy, ¬Rxy. These relations have probability 1, 0, p, 1 − p respectively. The probability of Q_{H}^{G}ϕ(x, y) is the probability of finite graph being in H with respect to the associated edge probability.

Dawar and Gradel go on to much more interesting results. They show in particular that F 0[rigid] has the 0-1 law for p = 1/2.